package org.datastructure.secondday.sort;

import java.util.Arrays;

/**
 * 希尔排序本就是对插入排序的优化方案，通过差分组来高效完成插入排序
 * 如果复习的时候看不懂，可以直接去看插入排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 通过位移的方式插入排序
     *
     * @param arr
     */
    public static void shellSort1(int... arr) {
        int stemp = 0;
        // TODO: 2021/7/6 分组
        for (int step = arr.length / 2; step > 0; step /= 2) {

            // TODO: 2021/7/6 无序从左到右比较
            for (int i = step; i < arr.length; i++) {

                // TODO: 2021/7/6 有序数组分组并从右到左比较
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]) {
                        stemp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = stemp;
                    }
                }
            }

        }
    }

    /**
     * 通过直接插入，实现排序
     * TODO 如果复习的时候看不懂，可以直接去看插入排序
     *
     * @param arr
     */
    public static void shellSort2(int... arr) {

        // TODO: 2021/7/6  分组
        for (int step = arr.length / 2; step > 0; step /= 2) {
            // TODO: 2021/7/6  无序数组从左向右依次与有序数组从右向左排序
            for (int i = step; i < arr.length; i++) {
                // TODO: 2021/7/6 分组并从右向左与无序数组比较
                int insertVal = arr[i];
                int insertIndex = i - step;
                // TODO: 2021/7/6 如果无序元素不小于有序元素，直接跳过，进行下一个无序元素比较
                if (insertVal < arr[insertIndex]) {
                    while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                        arr[insertIndex + step] = arr[insertIndex];
                        insertIndex -= step;
                    }
                    if (insertIndex + step != i) {
                        arr[insertIndex + step] = insertVal;
                    }
                }
            }
        }
    }
}
